import java.util.*;
public class Solution {
    //1. 前 K 个高频元素(map + 堆)
    public int[] topKFrequent(int[] nums, int k) {
        //哈希表
        Map<Integer, Integer> map = new HashMap<>();
        //全放入哈希表中，并统计个数
        for(int i = 0; i < nums.length; i++){
            if(!map.containsKey(nums[i])){
                map.put(nums[i], 1);
            }else{
                map.put(nums[i], map.get(nums[i]) + 1);
            }
        }
        //优先级队列(小根堆)
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer o1, Integer o2){
                return map.get(o1) - map.get(o2);
            }
        });
        for(Integer key : map.keySet()){
            if(queue.size() < k){
                queue.add(key);
            }else if(map.get(queue.peek()) < map.get(key)){
                queue.poll();
                queue.add(key);
            }
        }
        int[] ret = new int[k];
        //放入数组
        for(int i = 0; i < k; i++) {
            ret[i] = queue.poll();
        }
        return ret;
    }
    //2.每日温度(单调栈法)
    public int[] dailyTemperatures(int[] temperatures) {
        //建立一个单调递减栈
        Stack<Integer> stack = new Stack<>();
        int len = temperatures.length;
        int[] ret = new int[len];
        for(int i = 0; i < len; i++){
            while(!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]){
                ret[stack.peek()] = i - stack.peek();
                stack.pop();
            }
            stack.add(i);
        }
        //到了这里有两种可能，有可能全表示完了，也有可能还有剩下的0
        while(!stack.isEmpty()){
            ret[stack.pop()] = 0;
        }
        return ret;
    }
    //3.寻找旋转排序数组中的最小值(二分查找)
    public int findMin(int[] nums) {
        //二分查找定域，把握一个点，中间元素大于最左边元素，左边有序，右边一样
        //所以二分查找就是查找右边有序的区域
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < nums[right]){//右边有序
                right = mid;
            }else if(nums[mid] > nums[right]){//右边无序
                left = mid + 1;
            }else{
                break;
            }
        }
        return nums[left];
    }
    //4.最接近的三数之和(排序+双指针)
    public int threeSumClosest(int[] nums, int target) {
        //排序 + 双指针
        Arrays.sort(nums);
        //初始化和
        int sum = nums[0] + nums[1] + nums[2];
        for(int i = 0; i < nums.length - 2; i++){
            int left = i + 1;
            int right = nums.length - 1;
            while(left < right){
                int ans = nums[left] + nums[right] + nums[i];
                //比较更接近的
                if(Math.abs(ans - target) < Math.abs(sum - target)){
                    sum = ans;
                }
                if(ans < target){//这种情况，可以增大left
                    left++;
                }else if(ans > target){//可以减小right;
                    right--;
                }else{
                    return target;
                }
            }
        }
        return sum;
    }
    //5.最长连续序列(哈希表)
    public int longestConsecutive(int[] nums) {
        //哈希表
        //哈希表先去重
        Set<Integer> hash = new HashSet<>();
        for(int i = 0; i < nums.length; i++){
            hash.add(nums[i]);
        }
        //遍历哈希表，通过判断x - 1个数是否存在来定位最长连续序列的起始位置
        //同时减少了没必要的查找
        int count = 0;
        for(Integer key : hash){
            int tmp = 1;
            if(!hash.contains(key - 1)){//找到起始位置，就向后找最大长度
                while(hash.contains(key + 1)){
                    key++;
                    tmp++;
                }
                count = Math.max(count, tmp);
            }
        }
        return count;
    }
    //6.缺失的第一个正数(哈希表)
    public int firstMissingPositive(int[] nums) {
        //用set存入,去重
        Set<Integer> hash = new HashSet<>();
        for(int i = 0; i < nums.length; i++){
            hash.add(nums[i]);
        }
        //与自然数对比
        for(int i = 1; i <= Integer.MAX_VALUE; i++){
            if(!hash.contains(i)){
                return i;
            }
        }
        return -1;
    }
    //7.乘积最大子数组
    public int maxProduct(int[] nums) {
        //判断有偶数个负数还是奇数个负数
        //分别从两头计算，到最后一个负数停止，谁大就返回谁
        int sum = 1;
        int max = nums[0];
        for(int i = 0; i < nums.length; i++){
            sum *= nums[i];
            if(sum > max){
                max = sum;
            }
            if(sum == 0){
                sum = 1;
            }
        }
        sum = 1;
        for(int i = nums.length - 1; i >= 0; i--){
            sum *= nums[i];
            if(sum > max){
                max = sum;
            }
            if(sum == 0){
                sum = 1;
            }
        }
        return max;
    }
    //8.寻找重复数(哈希表)
    public int findDuplicate(int[] nums) {
        //哈希表
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length; i++){
            if(!set.contains(nums[i])){
                set.add(nums[i]);
            }else{
                return nums[i];
            }
        }
        return -1;
    }
    //9.删除有序数组中的重复项 II(排序法)
    public int removeDuplicates(int[] nums) {
        //记录超出范围的数，全部成整数的最大值，最后在排序
        int sum = 0;//总共有多少个数超出范围，最后用数组长度减去这个数就是所求
        int count = 1;//记录每个数出现的次数
        for(int i = 0; i < nums.length; i++){
            if(i + 1 < nums.length && nums[i] == nums[i + 1]){
                count++;
            }else{//可能越界，也可能下一个数和当前数不一致
                count = 1;
                continue;
            }
            if(count > 2){
                sum++;
                nums[i] = Integer.MAX_VALUE;
            }
        }
        Arrays.sort(nums);
        return nums.length - sum;
    }
    //9.删除有序数组中的重复项 II(快慢指针)
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        if(len <= 2){
            return len;
        }
        //快慢指针解决
        int fast = 2;
        int slow = 2;
        while(fast < len){
            if(nums[slow - 2] != nums[fast]){
                nums[slow++] = nums[fast];
            }
            fast++;
        }
        return slow;
    }
    //10.和为 K 的子数组(暴力)
    public int subarraySum(int[] nums, int k) {
        //暴力
        int count = 0;
        int len = nums.length;
        for(int i = 0; i < len; i++){
            int sum = 0;
            for(int j = i; j < len; j++){
                sum += nums[j];
                if(sum == k){
                    count++;
                }
            }
        }
        return count;
    }
    //11.寻找峰值(二分法)
    public int findPeakElement(int[] nums) {
        //因为边界都是负无穷，所以二分查找只需要向高处走，就一定会有山峰
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            int mid = (left + right) / 2;
            //说明峰值在右边
            if(nums[mid] < nums[mid + 1]){
                left = mid + 1;
            }else{//说明峰值在左边，也可能就是mid
                right = mid;
            }
        }
        return left;
    }
}
